package ch04;

import java.util.Stack;

//有向图寻找环
public class DirectedCycle {
    private boolean[] marked;
    private boolean[] onStack;
    private int[] pathTo;
    private Stack<Integer> stack;

    public DirectedCycle(DiGraph graph) {
        int v = graph.V();
        marked = new boolean[v];
        onStack = new boolean[v];
        pathTo = new int[v];
        stack = new Stack<>();
        for (int i = 0; i < v; i++) {
            if (!marked[i]) {
                DFS(graph, i);
            }
        }

    }

    public boolean isCycle() {
        return !stack.isEmpty();
    }

    public Stack<Integer> getStack() {
        return stack;
    }

    public void DFS(DiGraph graph, int v) {
        marked[v] = true;
        onStack[v] = true;
        for (Integer w : graph.adj(v)) {
            if (isCycle()) {    //==> !stack.isEmpty()
                return;
            } else if (!marked[w]) {
                pathTo[w] = v;
                DFS(graph, w);
            } else if (onStack[w]) {    //说明有环
                stack = new Stack<>();
                //记录环节点形成的路径
                for (int t = v; t != w; t = pathTo[t]) {
                    stack.push(t);
                }
                stack.push(w);
                stack.push(v);
            }
        }
        onStack[v] = false;
    }

    public static void main(String[] args) {
        DirectedCycle dc = new DirectedCycle(DiGraph.getDigGraph());
        System.out.println(dc.isCycle());
        Stack<Integer> stack = dc.getStack();
        while (!stack.isEmpty()) {
            System.out.println(stack.pop());
        }

    }
}
